package com.gp.gback.system.common.util;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 算法工具
 */
public class AlgorithmicUtil {
    /**
     * 获取数组的所有无序排列组合
     * @param arr
     * @return
     */
    public static ArrayList<List<String>> combination(String arr[]){
        ArrayList<List<String>> rs = new ArrayList<>();
        if(arr.length == 0) return new ArrayList<>();

        Stack<String> stack = new Stack<String>();
        for(int i = 1; i <= arr.length; i++){
            combine(arr, 0, i, stack,rs);
        }
        return rs;
    }

    public static ArrayList<List<String>> sizLimitCombination(String arr[],int targetSize){
        ArrayList<List<String>> rs = new ArrayList<>();
        ArrayList<List<String>> allCombinations = combination(arr);
        for (List<String> combination:allCombinations){
            if(combination.size() == targetSize){
                rs.add(combination);
            }
        }

        return rs;
    }


    //从字符数组中第begin个字符开始挑选number个字符加入list中
    private static void combine(String []chs, int begin, int number, Stack<String> stack,ArrayList<List<String>> rs){
        if(number == 0){
            ArrayList<String> subRs =  new ArrayList<>();
            for(int i=0;i<stack.size();i++){
                subRs.add(stack.get(i));
            }
            rs.add(subRs);
            return ;
        }
        if(begin == chs.length){
            return;
        }
        stack.push(chs[begin]);
        combine(chs, begin + 1, number - 1, stack,rs);
        stack.pop();
        combine(chs, begin + 1, number, stack,rs);
    }

    /**
     * 笛卡尔组合
     * @param src
     * @return
     */
    public static List<List<String>> decare(List<List<String>> src) {
        List<List<String>> result = new ArrayList();
        //中间有某个用下做笛卡尔组合的列表为空，不满足组合条件，直接返回
        for(List<String> strings : src) {
            if (strings == null || strings.size() == 0) return result;
        }
        decare(src,0,new ArrayList<>(),result);

        return result;
    }

    public static void decare(List<List<String>> src, int index, List<String> temp, List<List<String>> result) {
        //到达数组末尾
        if(index == src.size() ) {
            if(temp.size() != 0) {
                result.add(new ArrayList<>(temp));
            }
            return ;
        }

        for(String str : src.get(index)) {
            temp.add(str);
            decare(src,index+1,temp,result);
            temp.remove(temp.size()-1);
        }
    }

}
